\section{Evaluation}
\label{sec:evaluation}

\subsection{Calculating the dice}

As described, the OPs calculate the dice by exchanging hashes and seed parts. If the protocol succeeds, and at least one OP has chosen a random seed part, we have a secure result, i.e. no OP can have had any influence of the result. This is because we use a secure hash function, so no adversarial OPs can in reasonable time construct two different seed parts that has the same hash value.

Also note that the OPs have to calculate a new seed before each dice roll, because otherwise an adversarial OP could reveal the next dice rolls to some player.

There is however a problem with our approach: when an adversarial OP knows the result and does not like it, he can let the protocol fail. The problem may be reduced by kicking out an OP if the other OPs finds that he repeatedly lets the protocol fail. However, Awerbuch descibes an algorithm with which it is possible to design an elementary and sufficiently unbiased distributed random number generator that even works for public channels and a constant fraction of adversarial peers \cite{Awerbuch}.

\subsection{The purpose of having OPs}
One might ask why we use OPs instead of just letting the involved players handling everything in a particular game. The involved players might as well validate the moves and roll the dice. There may seem to be no reason for introducing the OPs. However there is a way of cheating that we cannot see how to solve without using OPs:

A player who is about to loose can throw away all messages that he is receiving by his opponent and claim that he is not receiving anything. The cheating player can claim that his opponent is about to loose and accuse him for not sending his next move.

Introducing the OPs solves this problem. Since the majority of the OPs are honest they will not throw away the messages from the winning player. If the loosing player refuses to make his next move, the winning player can use the OPs to prove that he has won. 

For a single game of Ludo, a player may not care to get a proof from the OPs that you have won - it may be enough satisfaction to know that the player were in the winning position, and that the loosing player abandoned the game. However, proof of victory would be necessary if the game system were to feature some kind of highscore. Additionally, a more advanced game with several sub-games might make the proof of victory of each sub-game necessary.

\subsection{Injection of OPs}

The security of our system basically relies on the IDs of the players: since the selection of the OPs is eventually a deterministic function of the participating players, and adversary could choose his ID such that he would be in control of the majority of the resulting OPs. To avoid this kind of attack, it should not be possible for a peer to choose his own ID.

In the system's current implementation, the ID's are simply chosen randomly, which does not assure the integrity of a player's ID.

One solution suggested in Sit would be to make a player's ID a function of his IP address \cite{Sit}. This can be a problem if an adversary controls a lot of IPs. He might then be able to control a game by creating peers that will be OPs of the game. For instance, an adversary might be able to get control of a whole subnet of approximately 65,000 IPs.

The probability of controlling enough OPs to control a particular game depends on the size of the network, the number of IPs the adversarial controls, the number of OPs for a game and the number of OPs needing to agree in a game. Appendix \ref{sec:prob_calc} lists a small program for calculating that probability. If, for instance, an adversarial wanting to control 3 out of 5 OPs has a subnet of 65,000 IPs, and the size of the network is 650,000, then the probability of getting control of that particular game is about 0,8\%. 

This may or may not be a problem: If the adversary knows all IDs currently in the network then he could pick opponents such that he can control the game. If he only knows few IDs in a big network with a lot of OPs per game, and the adversary wants to control most of them, then it is not a problem.

Another problem with using IP based IDs is of course that several
potential users behind the same IP address can only have access to one
peer.

\subsection{Spoofing}

In its current implementation, the system uses plain text messages. However, in order to avoid spoofing of messages by simply changing the sender of a message, there should be some way of authenticate messages.

If we consider the above mentioned solution, where a peer's ID is a function of his IP, a peer A wanting to confirm a message from peer B could send a message directly to the IP of peer B, asking him to confirm. However, an adversary with the ability to listen in on the communication could still forge a confirmation.

\subsection{Improving security with PKI}

A more robust solution to avoid OP injection and to prevent spoofing would be to introduce a PKI system: If a peer's ID is a function of his public key, he must have access to a lot of identities in the PKI to be able to control the majority of OPs in a game. Additionally, a PKI system would also enable message authentication. In order to avoid introducing a single point of failure, a decentralized organization of the PKI is an advantage \cite{Woelfl}.

\subsection{Supporting player rating}

It could be interesting to support a kind of player rating or overall highscore. We again consider two approaches as with the OP injection and spoofing: one where PKI is used for generating a peer's ID and one where IDs are hashes of a peer's IP:

\begin{itemize}

\item \emph{with PKI:}
\\
As explained earlier, using a PKI, each player would be able to control only one or very few peers. We could then hash the peer's ID to get 5 peers (rating OPs) that should store that peer's rating. When a Ludo game has finished, the OPs of the game should tell the rating OPs the result.

The rating OPs would of course be a weak link, since it would be favourable for an adversary to bribe the raiting OPs in order to get a good rating, compared to bribing OPs for a single game.

Alternatively, each player could store his own rating himself, and an auditing system very much like ARA could be implemented to check that no player is cheating with his own rating \cite{Ham}. A difference between this and ARA is that in ARA you loose your rating over time if you don't spend it. In our system we would probably like the rating to reflect the whole history of games.

Also, churn is a problem (as it is in ARA) since the peers needed for verifying come and go. A solution could be to combine the idea of an auditing system with the idea of replicated rating OPs.

\item \emph{without PKI, IDs are hashes of IPs:}
\\
If the IDs are hashes of IPs, it would be much more difficult to implement a rating system: the above solution with 5 rating OPs wouldn't work, since a peer controlling a subnet could easily find an ID, which would hash to rating OPs that he himself could control.

Instead, our best suggestion is that after a game had finished, the OPs of the game should store the result of the game forever. In this way, a peer who has lost a game cannot deny that he has lost that particular game.

However, an adversary with control of a subnet of 65,000 IPs could easily cheat: he could simply let one of his peers play and win over his other peers, in order to boost that peer's rating.
\end{itemize}

\subsection{Reprisal for cheaters}

Currently, there is no penalty for not following the protocol. For instance, a lazy peer who doesn't want to be OP for a certain game could simply lock up the game by not responding to messages for the game. Another example is for a loosing peer to send inconsistent moves to all OPs and thereby disrupting the game. A solution to these issues could be to give a lazy or disrupting peer a bad reputation since these violations of the protocol are not hard to detect. We have not dealt with this in great detail, but solutions for supporting reputation-based trust exist \cite{Xiong}.

\subsection{Our experiences with FreePastry}

In FreePastry a Message object is used to represent a message. The FreePastry tutorial states that by default FreePastry uses Java serialization \cite{freepastry}. However we found out that when an Application sends a Message to another Application running on the same machine, the object never gets serialized, meaning that one ends up having two references to the same object. That surprised us and gave us some problems until we realized this.

Apart from that FreePastry worked as we expected.

